package Z.dailyExercise.May;

public class _236二叉树的最近公共祖先 {

    /*
     二叉树搜索 判断是否分别在左右
     ===写复杂了

     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (findNode(root.right,p)&findNode(root.right,q)){
            lowestCommonAncestor(root.right,p,q);
        }else if (findNode(root.left,p)&&findNode(root.left,q)){
            lowestCommonAncestor(root.left,p,q);
        }else if ((findNode(root.left,p)&&findNode(root.right,q)) || (findNode(root.left,q)&&findNode(root.right,p))){
            return root;
        }else if ((root.val == p.val) && (findNode(root.left,q)|| findNode(root.right,q))){
            return root;
        }else if ((root.val == q.val) && (findNode(root.left,p)|| findNode(root.right,p))){
            return root;
        }
        return null;

    }
    public boolean findNode(TreeNode root,TreeNode node){
        if (root == null){
            return false;
        }

        if (root.val == node.val){
            return true;
        }else {
            return findNode(root.left,node)||findNode(root.right,node);
        }

    }

    /*
    同思路题解
    要是不在左右两侧 那必然在一侧
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root==p || root==q){
            return root;
        }

        if (root!= null){
            TreeNode atLeft = lowestCommonAncestor1(root.left,p,q);
            TreeNode atRight = lowestCommonAncestor1(root.right,p,q);

            if(atLeft != null && atRight!= null){
                return root;
            }else if (atLeft!= null){
                return atLeft;
            }else if (atRight!= null){
                return atRight;
            }
        }

        return null;
    }
}
